package com.fanco.learn_datastruct_leetcode.leetcode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
/**
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
 * <p>
 * input: intervals = [[1,3],[2,6],[8,10],[15,18]]
 * output: [[1,6],[8,10],[15,18]]
 */
public class Day27 {
    public static void main(String[] args) {
        Solution solution = new Solution();
    }
    private static class Solution {
        public int[][] merge(int[][] intervals) {
            if (intervals.length == 0) {
                return new int[0][2];
            }
            Arrays.sort(intervals, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0] - o2[0];
                }
            });
            List<int[]> merged = new ArrayList<>();
            for (int i = 0; i < intervals.length; i++) {
                int l = intervals[i][0]; // 当前元素左边区间
                int r = intervals[i][1]; // 当前元素右边区间
                // 如果结果集数组 为空 或者 结果集的 最后一个元素的 的右边值  比 当前元素的 左元素都小。
                if (merged.size() ==0 || merged.get(merged.size()-1)[1] < l) {
                    merged.add(new int[]{l, r});
                } else {
                    // 当前元素左区间 已经在 结果集中
                    // 比较右边值就可以了。取比较大的 放在 结果集 右边。
                    merged.get(merged.size()-1)[1] = Math.max(merged.get(merged.size()-1)[1] , r);
                }
            }
            return merged.toArray(new int[merged.size()][]);
        }
    }
}
